/*
 * @Author: liusheng
 * @Date: 2022-04-27 16:02:25
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-27 16:08:45
 * @Description: three order to traverse binary Tree
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 */

#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
先序遍历
*/
//1.递归
void preorderTra(TreeNode* root, vector<int>& nodes) {
    if (root == nullptr) {
        return;
    }
    nodes.push_back(root->val);
    preorderTra(root->left, nodes);
    preorderTra(root->right, nodes);
}

//2.迭代
void preorderTra(TreeNode* root, vector<int>& nodes) {
    stack<TreeNode*> sta;
    TreeNode* cur = root;
    while (cur != nullptr || !sta.empty()) {
        while (cur != nullptr) {
            nodes.push_back(cur->val);
            sta.push(cur);
            cur = cur->left;
        }

        cur = sta.top();
        sta.pop();
        cur = cur->right;
    }
}


/*
中序遍历
*/
//1.递归
void inorderTra(TreeNode* root, vector<int>& nodes) {
    if (root == nullptr) {
        return;
    }
    inorderTra(root->left, nodes);
    nodes.push_back(root->val);
    inorderTra(root->right, nodes);
}

//2.迭代
void inorderTra(TreeNode* root, vector<int>& nodes) {
    stack<TreeNode*> sta;
    TreeNode* cur = root;
    while (cur != nullptr || !sta.empty()) {
        while (cur != nullptr) {
            sta.push(cur);
            cur = cur->left;
        }

        cur = sta.top();
        sta.pop();
        nodes.push_back(cur->val);
        cur = cur->right;
    }
}


/*
后序遍历
*/
//1.递归
void postorderTra(TreeNode* root, vector<int>& nodes) {
    if (root == nullptr) {
        return;
    }
    postorderTra(root->left, nodes);
    postorderTra(root->right, nodes);
    nodes.push_back(root->val);
}

//2.迭代
void postorderTra(TreeNode* root, vector<int>& nodes) {
    stack<TreeNode*> sta;
    TreeNode* cur = root;
    TreeNode* prev = nullptr;
    while (cur != nullptr || !sta.empty()) {
        while (cur != nullptr) {
            sta.push(cur);
            cur = cur->left;
        }

        cur = sta.top();
        if (cur->right != nullptr && cur->right != prev) {
            cur = cur->right;
        }
        else {
            sta.pop();
            nodes.push_back(cur->val);
            prev = cur;
            cur = nullptr;
        }   
    }
}